package demo;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:复习快速排序非递归，归并排序递归版，归并排序非递归版，计数排序
 * User: 石方旭
 * Date: 2022-06-20
 * Time: 22:11
 */
public class TestDemo3 {

    //交换函数
    public static void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    //前后指针法
    public static int Partition(int[] nums,int left,int right){
          int prev = left;
          int cur = left+1;
          int pivot = left;
          while(cur<=right){
              if(nums[cur]<nums[pivot]&& ++prev!=cur){
                  swap(nums,prev,cur);
              }
              ++cur;
          }
          swap(nums,pivot,prev);
          return prev;
    }
    public static void QuickSort(int[] nums,int left,int right){
        if(left>=right){
            return;
        }
        int mid = Partition(nums,left,right);
        QuickSort(nums,left,mid-1);
        QuickSort(nums,mid+1,right);
    }

    //快速排序非递归版本
    public static void QuickSortNor(int[] nums,int left,int right){
        Stack<Integer> stack = new Stack<>();
        int mid = Partition(nums,left,right);
        if(left<mid-1){
            stack.push(left);
            stack.push(mid-1);
        }
        if(right>mid+1){
            stack.push(mid+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            mid = Partition(nums,left,right);
            if(left<mid-1){
                stack.push(left);
                stack.push(mid-1);
            }
            if(right>mid+1){
                stack.push(mid+1);
                stack.push(right);
            }
        }
    }

    //复习归并排序
    public static void MergeSort(int[] nums,int left,int right){

    }

    public static void main(String[] args) {
        int[] nums = {6,1,2,7,9,3,4,5,10,8};
        QuickSortNor(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
    }

}
